﻿#pragma once
#include "Index.h"

class ISearchInsertPosition
{
public:
	/**
	 * 搜索插入位置.
	 * 数组 二分
	 * https://leetcode.cn/problems/search-insert-position/
	 *
	 * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
	 * 请必须使用时间复杂度为 O(log n) 的算法。
	 * nums 为 无重复元素 的 升序 排列数组
	 */
	virtual  int searchInsertPosition(std::vector<int>& nums, int target) = 0;
};
class SearchInsertPosition
{
public:
	class Binary:public ISearchInsertPosition
	{
	public:
		/**
		 * 利用二分搜索在nums中找到第一个大于等于target的数字的位置，
		 * target已存在的位置或欲插入的位置就是找到的位置
		 */
		int searchInsertPosition(std::vector<int>& nums, int target) override
		{
			if (nums.empty())
				return 0;
			const int numsSize = nums.size();

			int resultPos = numsSize;
			int left = 0, right = numsSize - 1;

			while (left <= right)
			{
				const int mid = (left + right) >> 1;
				if (nums[mid] >= target)
				{
					resultPos = mid;
					right = mid - 1;
				}
				else
				{
					left = mid + 1;
				}
			}
			return resultPos;
		}
	};
};
